import java.util.HashMap;

/**
 * @program: LeetCode
 * @description: LeetCode : 剑指 Offer II 065. 最短的单词编码
 * @author: WXY
 * @create: 2023-01-08 15:16
 * @Version 1.0
 **/
public class offer_twentytwo1_minimumLengthEncoding {

    public static int minimumLengthEncoding(String[] words) {
        Trie root = new Trie();
        HashMap<Trie, Integer> map = new HashMap<>();
        for (int i = 0; i < words.length; i++) {
            String word = words[i];
            Trie cur = root;
            for (int j = word.length() - 1; j >= 0; j--) {
                cur = cur.get(word.charAt(j));
            }
            map.put(cur, i);
        }
        int ans = 0;
        for (Trie node : map.keySet()) {
            if (node.count == 0) {
                ans += words[map.get(node)].length() + 1;
            }
        }
        return ans;
    }


    //建立前缀树，不过是将words 中的 word从后往前添加到前缀树中，并将其在words中的位置记录在map中，
    //如果words[i] 是 添加到前缀树中的某个单词的前缀，就不用继续添加了，
    //累加添加到前缀树中单词的长度。map 中key 是添加到前缀树中叶子节点，也就是最后一个节点，所以count是0，

    public static void main(String[] args) {
        String[] words = {"me", "time"};
        int i = minimumLengthEncoding1(words);
        System.out.println(i);

    }

    public static int minimumLengthEncoding1(String[] words) {
        TrieNode root = new TrieNode();
        HashMap<TrieNode, Integer> map = new HashMap<>();
        for (int i = 0; i < words.length; i++) {
            String word = words[i];
            TrieNode curInsert = root.insert(word);
            map.put(curInsert, i);
        }
        int ans = 0;
        for (TrieNode node : map.keySet()) {
            if (node.isEnd) {
                ans += words[map.get(node)].length() + 1;
            }
        }
        return ans;
    }

    static class Trie {
        Trie[] child;
        int count;

        public Trie() {
            child = new Trie[26];
            count = 0;
        }

        public Trie get(char ch) {
            Trie cur = this;
            if (cur.child[ch - 'a'] == null) {
                cur.child[ch - 'a'] = new Trie();
                cur.count++;
            }
            return cur.child[ch - 'a'];
        }
    }

    static class TrieNode {
        TrieNode[] child;
        boolean isEnd;

        public TrieNode() {
            child = new TrieNode[26];
        }

        public TrieNode insert(String str) {
            TrieNode cur = this;
            for (int i = str.length() - 1; i >= 0; i--) {
                int index = str.charAt(i) - 'a';
                if (cur.child[index] == null) {
                    cur.child[index] = new TrieNode();
                }
                cur.isEnd = false;
                cur = cur.child[index];
            }
            cur.isEnd = true;
            for (int i = 0; i < 26; i++) {
                if (cur.child[i] != null) {
                    cur.isEnd = false;
                }
            }
            return cur;
        }
    }

}
